960 85208
132258368 179313760 225965562 160016501 342301210 911005612 704547076 385612389 880779873 418974850 986472738 995258630 374650307 120878072 520193748 512989325 904612788 980681605 158863263 581329365 878319339 268085125 382127246 681938139 760218083 825267641 986782893 891048259 777624923 722644420 854128013 64851666 14724823 898514863 372945348 16828401 310769948 576396389 83427689 267962417 554316472 812918328 379447452 360832705 371888759 105945946 195246076 856038138 381552111 615902821 216095535 379588820 597494 465223892 530515806 406609262 668678438 905906055 756507062 201165194 965840480 353091395 152120808 830180878 655625541 152733488 103314601 229040772 668602559 677064537 897356851 77340058 59438966 60864816 569454786 534026147 982791260 383710727 254859032 512099605 337962786 601652631 35554554 405678345 906032832 475906685 936383409 339087295 639951345 751925432 334201482 964602135 554095028 589354541 704604502 306950424 6470093 683665187 879039211 483971692 178492737 418524871 182359969 597116642 628649694 353668009 388925909 831146988 254989744 819677758 664628329 880778526 79479693 197806940 590346562 603909813 268594059 67912384 457981897 706920974 644661380 917969291 239454571 830460970 900210073 83577537 493415449 688133169 822074540 23492041 117005513 679048683 41093860 420430064 289569779 395739720 779240237 419791846 504221716 363044314 516512437 977604158 754053678 963419478 988964721 83827187 667476550 621326359 384057494 336851422 286735333 199916699 533060384 356816961 798078616 361435396 230634574 519295807 439497840 242883479 65370659 340069729 697936003 382574912 325159399 397294610 176339305 712351757 235799717 867108388 564877247 43699631 183537067 840072778 981668008 245779964 968220428 641879451 337734215 634985327 964270625 36323350 979402822 639870886 817583619 977067800 841371730 366742499 229299219 468330983 225138332 910134156 892492915 60068907 882357849 599387820 307305099 891939439 449701955 632857199 528516996 320725669 200090391 238460842 857973456 602875039 767063061 694914384 472650912 339988631 698571651 289820414 660549228 548336040 868055338 569580912 988988271 236976722 149576407 589386505 611407657 960868602 275868891 334778448 346529755 950383719 813493388 656753773 151927566 901988934 663509698 591701936 790046733 125142952 302646363 748532747 406083174 692058495 459988663 686149011 447393900 905197348 632044092 374675203 1658808 111034580 692717267 188924984 301922212 763896878 562713193 259629750 17802191 274568886 827960687 278385185 442645660 125112406 849319259 634389189 235903410 821804504 227213093 721784335 43781245 6623085 1305547 435110162 271195307 146737961 131708109 982777604 504193201 491586948 609446065 259102654 474007620 412193754 876663168 913127998 322765024 206931180 722019143 71198504 705359429 157843806 759077528 999168833 937147636 201393719 204655878 761342963 544084662 459465059 825629100 696391117 856998678 870863924 533156263 451521280 231132642 227583965 100893335 655504866 505323949 432826870 699030306 236773743 872706128 712392955 623351665 83783107 799549797 991055053 746615218 945368225 269018315 688876847 546696852 72151023 888062757 748085322 183191502 655604280 202486874 540015401 64386200 845012265 901507606 35723326 632093231 209642516 237597256 883099611 518884950 247149168 520812962 56482490 874100176 815546454 563135517 683767926 26916071 828110086 899773810 585858575 65941992 527194976 398453153 200920170 353060261 833132 602567534 910411471 880442865 295856594 775874783 341001065 715848231 759055458 809258944 767061962 1649060 866338958 697253919 138456932 495178825 909612779 3804880 525436433 252431098 785489076 227009513 637739659 414357537 768470599 145710407 134026997 339561003 878804389 290071304 534191440 139362826 155468534 704034319 633583111 64459697 985700099 419504772 291232868 146413723 422724027 397353041 469291800 962288709 673718446 536173990 793476279 488641200 415828885 65963381 132170809 834010336 685805768 2819574 29015931 180650335 592684486 31540005 730627004 380587706 122353585 102693695 876817952 30607875 980694991 964981577 323596848 145132877 891239434 76675465 771127896 490137140 345401201 522145291 258876520 199626322 547531445 417654045 703896084 392325067 162051757 608535507 911498612 619335106 507096274 942954628 603486085 206250209 958477251 84304202 600851621 585593302 76967875 806731398 847408411 43831760 653902646 557002075 279344013 604163334 580177704 541598254 991378311 360451376 320120262 36399404 725232635 602133004 151077602 844317380 181372348 790005210 477783667 304291881 523274241 138663393 217027347 813989841 652444393 647010536 693513855 175525368 984304113 673030589 95747611 617271582 715317375 218862514 572770667 655023237 153958491 424143643 403635867 125759156 504350256 522726353 82618616 487624694 766058512 554099122 593766773 86990556 238597101 496249118 509067047 90454711 515930657 240080764 498743753 523061279 599170023 412561843 279236665 2770287 258515935 662400177 280589049 349722950 698350222 276635624 178441391 748106503 627666140 464299980 455856293 646361434 671180948 397502550 759777610 539521705 945701607 992994180 345700527 352194980 99258089 451707350 284039434 532970941 844313619 146927315 16836406 538834349 484852927 229488002 322652978 390725613 398102191 703673585 356848798 213259070 612674951 919277746 512965953 981879074 773616462 383992153 176561541 542535776 298819825 761669375 207483129 911059843 861676224 393286082 875361998 300339036 729705711 324942915 636008539 684316540 357389847 798141478 270232474 918357179 464176562 475544213 438806952 557628340 777086114 661457086 573615432 694639942 801131946 519167568 852952417 915549972 605089779 708425218 363997564 349163526 967926665 117018637 335548487 637635782 983892444 637906604 774811668 213828676 151855168 136855203 262981978 411618355 942167149 335334326 368263987 461681545 306306815 394082605 952144349 357595395 64346103 532843094 59235641 28955551 438470456 503372547 491182415 298508063 187031819 437600264 748672712 427122317 663887515 777387454 213872499 230690481 19667578 366946947 152117952 539360413 540687131 967063352 661286472 765446178 556148053 911944641 48364099 389522008 836247782 226250121 815135760 695290906 485713646 443145723 510084273 756847751 748600432 202997002 341639500 983106435 68781780 721542570 996744107 643204660 709710440 141695572 574218941 902716293 523377882 765657478 6331155 272052390 218081727 703972417 635833187 857198985 660192016 275829385 27007241 308350823 434324392 726406633 54456961 449187642 239445959 48689132 137531374 585737280 619859346 157784741 579801495 181234814 899063184 334572328 777287780 295295803 492557614 625319950 170671717 258062720 71943997 941763062 215873867 572165279 778938991 976215038 962870509 643987625 962026973 473864782 817954245 817260790 838782852 129516685 799572337 846451361 242817219 697349226 671261490 847010570 973513438 605109780 487521904 871522386 569769854 125474498 446616884 641042914 966993711 909031213 954814636 127460068 859419617 523049489 792391594 19072200 920206696 947019440 815896358 799995841 714431484 129025358 338376888 197674822 860406458 740995510 397796638 870695569 652145184 385125299 850986172 662758179 342873237 619772824 215332887 276449598 691757791 306762425 605451353 974282346 470389930 184917488 753748433 128664048 122255112 121157145 349117552 238523746 312703724 136578198 957474380 76234513 897431470 975659979 921147936 906616981 29347722 484378531 119291338 617283914 141458464 503603721 590050508 37198029 402082038 587928944 160021709 578694018 6484977 599336268 443079701 813552401 671501792 975673495 794464788 481397477 18309361 373258829 75706331 996330668 940248378 565610480 405886625 438250202 197414193 780732420 786285631 635817253 239835188 111847060 646927797 260274442 395409667 530182059 571699619 632930375 995967041 97105884 147543248 399748447 863309558 317776571 779909287 177971737 606412559 925269858 695525301 677067777 678199261 261248237 951414317 725593830 915129490 53186302 17433188 339401050 499355335 94230586 534105429 893854518 236718329 15232713 5454621 403822099 38748423 721305818 47808896 659278289 927643830 364942621 432163427 724755732 86384173 299869511 255859791 936039362 607529081 47889553 87838965 505210246 43641354 57901626 564165029 425454672 198680372 850188288 806284245 394272979 295580336 796492971 255419808 1996550 606975000 767661699 587068484 363672228 54806638 557433300 940732067 487368108 973304469 294013809 381940675 96703713 535419863 489950510 168943438 591613514 73177693 879841893 706376211 717180339 44443578 695774322 988979331 943065899 521303905 332138295 463514932 196701060 867961130 81826713 390453602 785415895 774231505 90327553 190541673 43107581 533596023 545345243 101804876 537850902 111519775 210598682 249179441 76967686 919240754 656308914 303301091 87966195 641859324 482352413 829570895 832057545 610690860 615452631 377463559 113082294 597464920 237656802 841763522 508692398 32314999 712373059 644111578 828733160 855589989 212759939 266445004 570280287 831477346 425381934 612644284 431690578 746516371 305470039 506717422 698321348 990784384 678058003 621051982 732961020 117613716 613058809 172470505 272161542 860280993 501720233 590980466 948634161 466324825 906035010 908432574 88104336 399548118 231302633 424284232 223585145 777271827 824534345 201534638 283231752 308713840 96382478 339238450 503083933 972742962 956572521 536419641
966149466 230495232 46519183 928536271 158876070 574365543 970428474 721140514 492543148 82490455 103190310 100167683 201427677 806769061 226752149 61022056 846822250 895883399 30786508 767659500 497568458 919943451 801304468 199098702 553119034 354460384 388755641 317598958 500400440 728238394 339136654 676523603 66199560 381481458 119840616 541051303 822453295 560305588 84462879 704761401 400923642 48139920 239338384 982984954 737725432 737815162 59929373 989333249 235233660 128558026 96380203 62451719 202407708 621211581 367126178 407575788 83783989 493712114 405509745 493745200 327792228 39615981 5666824 855906426 80927758 493265815 391791581 259124501 958696153 192580028 500243944 95282798 389275953 59437452 367343654 574454423 568145348 823609882 562773785 782312903 43680262 591502048 359417926 540047064 23387310 648611385 968726710 362216392 724435511 773538278 853625717 34041400 42607456 544826762 234226711 554951664 767603116 361426222 902149422 514111321 312621539 752155069 939504853 675036673 996897935 360179081 546945320 479770907 519227520 359217860 920062665 134932476 597406025 700804616 516711773 987188383 712195008 699089104 358881805 137802274 945187970 898650620 755369478 204379975 701554284 288295505 563238137 565458676 888688931 141699319 721514395 418896051 622120845 28284409 904785958 662033715 798275670 760463561 351959255 328596165 547656301 39981241 669081198 863591392 913847684 335142786 897565361 987842461 890842259 271511489 976266473 9959995 819955797 622775157 831498338 716669852 147499977 193975939 871912688 782184391 701004978 304240434 555741541 898426724 154779672 403273391 164592668 695617091 114977477 207180170 218086257 688134101 346437065 377469496 880842311 199474609 41300727 356628367 148792960 739938833 785056613 455090508 882101640 823900754 140747248 980624016 395455179 482377592 796889014 344980063 427544635 696405159 570531994 878331936 840272075 520763819 705358275 681439776 973712118 253269873 453668893 342446095 325808952 348613772 309924054 704476545 580540564 123467697 581973474 225664622 121315085 752491579 868802168 603328946 911314988 200479399 876014484 152597390 571768704 204274969 279811699 822396965 551977242 78385622 676707097 836290560 350590477 167841736 268178638 569767562 523107060 950818045 974872732 315721877 459187820 529825576 150541267 255333076 533769621 434456095 360884358 32780895 90885269 198045787 505787404 581331250 849927957 898909051 600383871 727500461 931431618 704851649 733891136 334116373 714084813 15686035 707062385 2538258 21170540 10235387 889999737 841617967 829113943 829076776 853543556 596545886 562158411 502241771 187397377 216092785 250885514 684718907 853399842 72819106 668786521 373577905 296005727 770867724 888715393 323812621 578204659 612434479 139948240 977836207 484134750 494457968 831362709 990633502 461485281 913852310 540869414 619619461 21211141 277156686 744651613 219887153 283535380 6301865 137553943 448877332 208265886 345071257 834095284 417553221 459129334 306415735 588391834 738392958 771470259 871468672 502612658 573388189 747062575 80380499 111850985 612124963 651370507 366516597 816776625 638725048 987667625 867635149 972422525 172224933 904415921 167221288 598641224 731769944 579360141 601749686 403881231 75866340 764225260 901908875 831458130 172576894 819502915 205054751 900283799 500667137 997051463 241126094 509372903 680113003 102321012 984714585 614446160 747786846 766708361 888522084 840569697 901414048 684303370 296783862 881419952 482351515 435724733 443274491 991194456 100899293 884181805 551024581 444565107 104927641 320581162 234971015 409686437 234340645 936785223 672323033 509036945 414604666 452106331 267740471 912822881 404611767 430856449 591658370 872178754 480410271 555945752 286023293 592688613 863460118 152114499 328947793 337246976 789733543 368331625 367165961 688217803 217426689 926899510 27712023 178829956 993014133 121859225 619413709 492570091 156769146 997234756 32681189 728694726 761982762 701225007 164189690 497227870 686974914 949896726 95786765 980852225 802044966 484120054 86676224 703990654 621292378 431728788 265952030 176740524 298633994 718553590 975634833 892056291 251840003 301381607 41657835 337100160 170481335 238173303 359203230 608065126 936901566 43901049 474869892 403461240 10109520 30600708 774829399 75474976 204405451 316141811 702256698 766290379 25130803 388664677 148588846 563340395 866062253 45119037 547095198 999104500 975754499 484025763 314816980 5936607 530038051 771925889 202881921 490627497 971350944 389548038 935212089 873075029 24713263 840454183 389874932 264614374 82310956 868998169 290727823 413669350 572759059 878637528 581000009 448335331 293792262 525024164 895648582 864458988 826434638 423006847 110462224 281329432 443042514 940668080 309875984 839220735 80299169 102645314 307129113 447501119 79968367 942579078 557974238 809794296 866251535 84208524 927925367 245242448 616367614 613649582 771742945 178324977 520351704 329664262 805234298 305464454 578119904 869578995 519711113 813504321 935993725 841747864 235098804 427334744 746981559 410588509 14573447 697561475 788260030 334308460 515873524 407917184 31618916 699491637 1231822 605875088 924001438 879468778 598287180 112542711 450134790 596855812 185344397 807621247 323595868 896739516 470461966 493669366 734729216 710006163 136093749 674413995 751933306 635602378 596812746 261821429 855508723 193286123 166350712 342896812 279521721 957513278 751456081 354163630 600439487 400382293 597894471 625259356 825019162 46069889 700619188 721686810 549747845 276758618 605103571 127475154 640651742 687995194 438048836 270262385 841198503 48239042 56560524 422702185 577273478 767856981 641537171 366850094 606555077 74738328 15289636 697640889 593766866 624581113 645386352 366177032 269289664 267018276 194709387 913604764 336108741 351982735 269442030 879821817 970697914 163271663 418840563 331870761 402317982 804346049 68258652 882664506 322017811 56147907 19243469 750576059 873969375 599891063 840582989 304827203 662343021 17863591 69607625 481091306 637718346 913284059 776205457 141688526 926806440 724731365 458250969 194497424 536056286 507304790 716108346 303462100 955362277 344490246 366827054 946619333 365778653 931013520 115081111 643975054 623183238 263366611 66625336 235352034 381671623 675306354 53457978 684216692 491065387 36484949 178915497 458365568 759221343 353288230 731379701 886652225 228202422 991406293 408981362 104011384 967663269 817475349 57694936 967870956 264362567 607554524 315766979 457481956 960304857 268318695 294460212 854898351 627087935 48237107 820649998 799826716 453394558 460373637 934368666 208682242 306119744 781238755 935037187 951166138 599723347 555644697 399390427 585612960 927444266 549596470 108685717 957344149 444217178 496334348 14227464 565515136 279233054 620383923 461805554 319118792 181158100 548334598 711817331 4955611 743207038 909989156 140165774 895756203 756679746 707552753 79018923 877478956 199036907 838666642 266255384 426873304 815086693 407670517 118105987 107267883 457702980 775295303 518119810 939074342 525111870 308793467 957668363 42847184 3547564 832000970 538676220 324395696 975518478 937059373 398028180 154185045 572766852 94364901 137219832 508972494 217893461 415591412 510945967 793855282 252559212 981486753 981849126 79219226 50698198 828525560 571869230 498935074 393693509 810460488 353770361 538678635 84590480 701013155 464396064 636644124 851038513 653646689 116225824 811897308 715778501 849492125 636023512 785159514 498367120 217118134 448536972 173537734 833350390 849257168 859951333 486568021 298767619 837968209 21664111 163083712 283848676 564572260 88106266 867944133 526543468 561180537 732494778 686562469 280896912 801305795 48172423 934447013 341212395 595325880 998974878 541702541 745758523 327261589 345516669 943946284 280866530 999599064 326241931 215475665 879958630 643154116 21393550 267548627 577792753 237718496 11194418 590231307 608429265 459571832 356051081 891237973 601518073 260168731 518180998 889471763 345558143 500604699 458324865 665640361 932657948 542438672 804546998 16489474 509325231 864246101 946199237 226804746 686662586 680752010 500779060 703661105 814328035 882326032 375289320 598607342 420626805 315224208 860347056 792283194 41603292 128920693 63510714 686219281 9049644 650824045 319213084 120377077 182253211 989074923 308159820 767916906 233281027 960109480 616526248 923144571 180960097 347910686 77218800 812073268 530793817 763244300 616309959 362432805 369823407 435650293 776724789 104424166 927416527 840575392 88946471 634016141 270844998 975549593 553831406 400186425 355531078 693442991 516950204 391064203 906317350 105323380 887764266 1500456 164731360 226170816 18141109 763897912 740150930 841863215 39765052 781617130 74642429 691811486 463028356 307349742 500861961 961125810 68417716 993479929 630693183 914447185 945524697 984379717 477180749 390829862 784744547 881728782 694571910 15628065 482844326 855026198 343575903 14333941 961744219 892981025 901770996 381125017 900890140 962294906 736640384 175871944 856703979 677259885 372422632 807875200 842205099 814086091 3623729 425161351 396841126 931848297 488214790 852607457 63057157 670465440 254565427 222714459 278793819 695291087 619942700 907441668 151664667 996214740 819626631 346063278 887537693 378157463 670937469 809434994 312331549 124936320 568787566 778129705 370488636 72009468 630338394 123404531 214593661 467265531 26182760
